package com.yun;

/**
 * Created by lsy
 * 递归方法实现八皇后
 * on 2020/9/3 9:38.
 */
public class TheEightQueueRecursive {

    public int size;

    public static void main(String[] args) {
        int QUEUE_NUM = 12;
        int[] cols = new int[QUEUE_NUM];
        TheEightQueueRecursive solution = new TheEightQueueRecursive();
        long l = System.nanoTime();
        solution.placeQueue(0, cols);
        System.out.println("count :" + solution.size);
        System.out.println("cost time :" + (System.nanoTime() - l));
    }

    public void placeQueue(int i, int[] cols) {
        int num = cols.length;
        if (num - i == 0) {
            size++;
        } else {
            // 放置第i个
            for (int j = 0; j < num; j++) {

                if (isValid(cols, i, j)) {
                    // 最严重的，没有放置cols
                    cols[i] = j;
                    placeQueue(i + 1, cols);
                }
            }

        }
    }

    // 还需要知道放置的是第几行的，竖线，斜线不可以交叉
    private boolean isValid(int[] cols, int i, int j) {
        // 这里可以只遍历到i位置，因为后面列还没放置
        for (int k = 0; k < i; k++) {
//            if (cols[k] == j|| Math.abs(cols[k] -i) == Math.abs(j-cols[k])) {
            // 遍历行 和目标行 的差值 跟 遍历行防止的位置 和当前要放置的位置差值相同代表在一个斜线
            if (cols[k] == j || Math.abs(k - i) == Math.abs(j - cols[k])) {
                return false;
            }
        }
        return true;
    }
}
